from heapq import heapify, heapreplace
from typing import List


class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        # 优化思想：
        # 极端条件下，次数k的值 远大于 数组长度n，所以k可以重复k//n次操作 某一元素

        # 设把每个 nums[i] 都操作到至少为 nums 的最大值，总共需要操作 total 次。
        #
        # 分类讨论：
        #
        # 如果 k<total，那么直接用最小堆暴力模拟 k 次。
        #
        # 如果 k≥total，我们可以先把每个 nums[i] 暴力操作到 nums 的最大值，然后剩余的操作直接用公式计算。
        # 在把数组中的每个元素都操作到不小于当前最大值之后，剩下的操作次数 k 会均摊到数组的每个元素上。
        # 由于 k 不一定能被数组长度 n 整除，所以会出现两种情况：一部分元素会多进行一次操作，另一部分元素进行的操作次数相同。
        if multiplier == 1:  # 数组不变
            return nums

        MOD = 1_000_000_007
        n = len(nums)
        mn = min(nums)
        mx = max(nums)
        t = 0
        while mn < mx:
            # 把最小的值 操作到 最大值 需要t次
            mn *= multiplier
            t += 1

        if k < t * n:
            # 暴力模拟 出堆 进堆
            h = [(x, i) for i, x in enumerate(nums)]
            heapify(h)
            for _ in range(k):
                x, i = h[0]
                heapreplace(h, (x * multiplier, i))
            for x, j in h:
                nums[j] = x % MOD
            return nums

        # 每个数直接暴力操作到 >= mx
        for i, x in enumerate(nums):
            while x < mx:
                x *= multiplier
                # 更新剩余的操作次数
                k -= 1
            nums[i] = x

        # 剩余的操作可以直接用公式计算
        # 剩下的次数会均摊到数组中  k//n 均摊的次数
        pow1 = pow(multiplier, k // n, MOD)
        # 均摊后 多进行一次的操作
        pow2 = pow1 * multiplier % MOD
        # 对nums排序，目的是：保证在处理剩余操作次数时，优先给较小的元素多进行一次
        for i, (x, j) in enumerate(sorted((x, i) for i, x in enumerate(nums))):
            # i < k%n 用于判断 当前的元素是不是需要多进行一次操作的元素
            nums[j] = x * (pow2 if i < k % n else pow1) % MOD
        return nums